using System;
using System.Collections.Generic;
using System.Text;

namespace Hoshimi
{
    /// <summary>A PriorityQueue maintains a partial ordering of its elements such that the
	/// least element can always be found in constant time.  Put()'s and pop()'s
	/// require log(size) time.
	/// </summary>
	public abstract class PriorityQueueFast<T>
	{
		protected T[] heap;
		public int Count;
		protected int maxSize;

		/// <summary>Determines the ordering of objects in this priority queue.  Subclasses
		/// must define this one method.
		/// </summary>
		public abstract bool LessThan(T a, T b);

		/// <summary>Subclass constructors must call this. </summary>
		protected internal void  Initialize(int maxSize)
		{
			Count = 0;
			int heapSize = maxSize + 1;
			heap = new T[heapSize];
			this.maxSize = maxSize;
		}

		/// <summary> Adds an Object to a PriorityQueue in log(size) time.
		/// If one tries to add more objects than maxSize from initialize
		/// a RuntimeException (ArrayIndexOutOfBound) is thrown.
		/// </summary>
		public void  Push(T element)
		{
			Count++;
			heap[Count] = element;
			UpHeap();
		}

		/// <summary> Adds element to the PriorityQueue in log(size) time if either
		/// the PriorityQueue is not full, or not lessThan(element, top()).
		/// </summary>
		/// <param name="">element
		/// </param>
		/// <returns> true if element is added, false otherwise.
		/// </returns>
		public virtual bool Insert(T element)
		{
			if (Count < maxSize)
			{
				Push(element);
				return true;
			}
			else if (Count > 0 && !LessThan(element, Top()))
			{
				heap[1] = element;
				AdjustTop();
				return true;
			}
			else
				return false;
		}

		/// <summary>Returns the least element of the PriorityQueue in constant time. </summary>
		public T Top()
		{
			if (Count > 0)
				return heap[1];
			else
				return default(T);
		}

		/// <summary>Removes and returns the least element of the PriorityQueue in log(size)
		/// time.
		/// </summary>
		public T Pop()
		{
			if (Count > 0)
			{
				T result = heap[1]; // save first value
				heap[1] = heap[Count]; // move last to first
				heap[Count] = default(T); // permit GC of objects
				Count--;
				DownHeap(); // adjust heap
				return result;
			}
			else
				return default(T);
		}

		/// <summary>Should be called when the Object at top changes values.  Still log(n)
		/// worst case, but it's at least twice as fast to <pre>
		/// { pq.top().change(); pq.adjustTop(); }
		/// </pre> instead of <pre>
		/// { o = pq.pop(); o.change(); pq.push(o); }
		/// </pre>
		/// </summary>
		public void  AdjustTop()
		{
			DownHeap();
		}


		/// <summary>Returns the number of elements currently stored in the PriorityQueue. </summary>
		public int Size()
		{
			return Count;
		}

		/// <summary>Removes all entries from the PriorityQueue. </summary>
		public void  Clear()
		{
			for (int i = 0; i <= Count; i++)
				heap[i] = default(T);
			Count = 0;
		}

		protected void  UpHeap()
		{
			int i = Count;
			T node = heap[i]; // save bottom node
            int j = (int) (((uint) i) >> 1);
			while (j > 0 && LessThan(node, heap[j]))
			{
				heap[i] = heap[j]; // shift parents down
				i = j;
                j = (int) (((uint) j) >> 1);
			}
			heap[i] = node; // install saved node
		}

		protected void  DownHeap()
		{
			int i = 1;
			T node = heap[i]; // save top node
			int j = i << 1; // find smaller child
			int k = j + 1;
			if (k <= Count && LessThan(heap[k], heap[j]))
			{
				j = k;
			}
			while (j <= Count && LessThan(heap[j], node))
			{
				heap[i] = heap[j]; // shift up child
				i = j;
				j = i << 1;
				k = j + 1;
				if (k <= Count && LessThan(heap[k], heap[j]))
				{
					j = k;
				}
			}
			heap[i] = node; // install saved node
		}
	}
}
